package backtracking;

import java.util.*;

/**
 * 491.非递减子序列
 * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
 * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
 */
public class findSubsequences {

    /**
     * 一刷，建议看二刷
     */
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<>();
        backtrack(nums, 0, result, list);
        return result;
    }

    public void backtrack(int[] nums, int start, List<List<Integer>> result, List<Integer> list) {

        if (list.size() >= 2) {
            result.add(new ArrayList<>(list));
        }

        Set<Integer> usedInCurrentLevel = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if (usedInCurrentLevel.contains(nums[i])) {
                continue; // 跳过重复元素
            }
            if ((list.isEmpty() || list.getLast() <= nums[i])) {
                list.add(nums[i]);
                usedInCurrentLevel.add(nums[i]);
                backtrack(nums, i + 1, result, list);
                list.remove(list.size() - 1);
            }
        }
    }
    /**
     * 二刷，思想一样，代码更简洁，更能看出回溯思想体现
     */
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> findSubsequences(int[] nums) {
            backtracking(0, nums);
            return res;
        }

        public void backtracking(int start, int[] nums) {
            if (path.size() > 1) {
                res.add(new ArrayList<>(path));
            }
            HashSet<Integer> hs = new HashSet<>();
            for (int i = start; i < nums.length; i++) {
                if(!path.isEmpty() && path.get(path.size() -1 ) > nums[i] || hs.contains(nums[i]))
                    continue;
                path.add(nums[i]);
                hs.add(nums[i]);
                backtracking(i + 1, nums);
                path.removeLast();

            }
        }
    }
}
